/***********************************
 * 3、线性表A，采用链式存储结构，且按递增顺序排列，表头指针为H，
 * 请设计一个算法，如果值b的元素不存在，则将b添加到链表中。
 **************************************************/

#include<stdio.h>
#include<malloc.h>

struct NODE;
typedef struct NODE node;
struct NODE{int data;node* next;};

void print_linkedlist(const node* p){
    p=p->next;
    while(p){printf("%d ",p->data);p = p->next;}
    putchar('\n');
}

void add_value(node* h,int b){
    while(1){
        if(NULL == h->next || h->next->data > b){
            printf("Should add %d.\n",b);
            node* p = malloc(sizeof(node));
            p->data = b;
            p->next = h->next;
            h->next = p;
            return;
        }
        if(h->next->data==b)return;
        h = h->next;
    }
}


int main(){
    node head;
    node* h = &head;
    h->next = NULL;
    int n = 10, i = 0;
    int A[10] = {1,3,5,7,9,2,4,6,8,0};

    for(i=0;i<n;i++)add_value(h,A[i]);
    print_linkedlist(h);

    int test[4] = {-1,3,12,-18};
    for(i=0;i<4;i++){
        add_value(h,test[i]);
        printf("Try to add %2d. Now: ",test[i]);
        print_linkedlist(h);
    }

    // clean-up
    node* p;
    while(h){p = h;h=h->next;free(p);}
    return 0;
}